package org.forever.util
{
	
	/**
	* （有向）图的遍历算法模板
	*/
	public class GraphTraverse
	{
		/**尚未被发现的顶点*/
		public static const UNDISCOVERED:int = 0;
		/**已被发现的顶点*/
		public static const DISCOVERED:int = 1;
		/**已访问过的顶点*/
		public static const VISITED:int = 2;
		/**未知边*/
		public static const UNKNOWN:int = 0;
		/**树边*/
		public static const TREE:int = 1;
		/**横跨边*/
		public static const CROSS:int = 2;
		/**前向跨边*/
		public static const FORWARD:int = 3;
		/**后向跨边*/
		public static const BACKWARD:int = 4;
		
		/**图*/
		public var G:Graph;
		
		public function GraphTraverse(g:Graph) { G = g; }
		
		/**将G中各顶点的标志、各边的分类复位（s为遍历起点）*/
		public function reset(s:Vertex):void {
			for (var it:Iterator = G.vertices(); it.hasNext();) {//所有
				var v:Vertex = it.getNext() as Vertex;//顶点的
				v.setStatus(UNDISCOVERED);//状态置为UNDISCOVERED
				v.setDistance(int.MAX_VALUE);//最短距离初始化为无穷大
			}
			for (var it:Iterator = G.edges(); it.hasNext();)//所有边
			{(it.getNext() as Edge).setType(UNKNOWN);}//置为UNKNOWN
		}
		
		/**遍历过程中对顶点v的具体访问操作的模板：取决于、服务于具体的算法algorithm()*/
		protected function visit(v:Vertex, info:Object):Object{throw new Error("异常：该方法必须被子类实现"); }
		
		/**基于遍历操作实现的其它算法的模板：s为起始顶点，info向算法传递参数及保存算法的返回信息*/
		public function algorithm( s:Vertex, info:Object):Object{throw new Error("异常：该方法必须被子类实现");}
		
		/**遍历算法模板,从顶点v出发做遍历*/
		public function traverse(v:Vertex, info:Object):Object{throw new Error("异常：该方法必须被子类实现"); }
		
	}
}